package baoliDigui;
//给定货物和价值数组 给定背包容量  求最大价值
public class WeightAndValue {

    public static void main(String[] args) {
        int sum = 100;
        int[][] arrs = {
                {77, 92},
                {22, 22},
                {29, 36},
                {50, 46},
                {99, 90}};
        int[] weight = {77, 22, 29, 50, 99};
        int[] value = {92, 22, 36, 46, 90};
        System.out.println(getMaxValue(sum, arrs, 0));
        System.out.println(getMaxValueWithDP(weight, value, 100));
    }
    //01背包暴力递归版本




    public static int getMaxValue(int[] weight,int[] value,int index,int rest){
        //空间不足了
        if (rest<=0){
            return 0;
        }
        //货物完了
        if (index == weight.length){
            return 0;
        }
        //有货也有空间
        //不选取当前货物 后续获得的最高价值
        int p1=getMaxValue(weight, value, index+1, rest);
        int p2=Integer.MIN_VALUE;
        if (rest>=weight[index]){  //如果背包有足够空间
            //选取当前货物 后续获得的最高价值
            p2=value[index]+getMaxValue(weight, value, index+1, rest-weight[index]);
        }
        return Math.max(p1,p2);
    }

    //01背包改dp

    public static int getMaxValueWithDP(int[] weight,int[] value ,int rest){
        int[][] dp = new int[rest+1][weight.length+1];
        for (int j = weight.length-1;j>=0;j--){   //j代表轮询背包地址
            for (int i =1;i<=rest;i++){   //i代表剩下的空间
                int p1= dp[i][j+1];
                int p2= 0;
                int p3=0;
                if (i>=weight[j]){
                    p2= value[j] + dp[i-weight[j]][j+1];
                }
            dp[i][j] = Math.max(p1,p2);
            }
        }
        return dp[rest][0];
    }

    //完全背包暴力递归版本
    public static int getMaxValue(int sum,int[][] arrs,int index){
        //空间不足了
        if (sum<=0){
            return 0;
        }
        //货物完了
        if (index == arrs.length){
            return 0;
        }
        int p1=getMaxValue(sum, arrs, index+1);
        int p2=Integer.MIN_VALUE;
        int p3=Integer.MIN_VALUE;
        if (sum>=arrs[index][0]){  //如果背包有足够空间
            //选取当前货物 后续获得的最高价值
            p2=arrs[index][1]+getMaxValue(sum-arrs[index][0], arrs,index+1 );
            p3=arrs[index][1]+getMaxValue(sum-arrs[index][0], arrs,index);
        }
        int max = 0;
        max = Math.max(p1,Math.max(p2,p3));
        return max;
    }

    //完全背包改动态规划
    public static int getMaxValueWithDP01(int[] weight,int[] value ,int rest){
        int[][] dp = new int[rest+1][weight.length+1];
        for (int j = weight.length-1;j>=0;j--){   //j代表轮询背包地址
            for (int i =1;i<=rest;i++){   //i代表剩下的空间
                int p1= dp[i][j+1];
                int p2= 0;
                int p3=0;
                if (i>=weight[j]){
                    p2= value[j] + dp[i-weight[j]][j+1];
                    p3= value[j] + dp[i-weight[j]][j];
                }
                dp[i][j] = Math.max(p1,Math.max(p2,p3));
            }
        }
        return dp[rest][0];
    }
}
